\chapter{Experiment} \label{ch:experimental}
To experimental validate our proposed framework, we run our prototype application (Jasim, cf., \ref{sec:jasim}) on a case study of crisis management domain. Particularly, the case study focuses on the \emph{Fire fighting at a building}. In the following sections, we detail the case study constructed based on scenario in \cite{SPEARS-D21},

\section{Case Study: Fire fighting} \label{sec:CaseStudy-Fire}
\subsection{Scenario}
The fire happens in some location of a building. Fire warden of the building performs on-site reactions such as switch off gas/electricity and use fire-extinguishers. If the extinguishers are damaged by the fire, then it cannot be used. After fire trucks arrive to the scene, the fire commander wish to attack the fire. For the preparation, the police cordon area of bystanders. The two teams: Blue team and Green team will attempt scouting the building to locate the seat of fire and locate the place of trapped victim. The Red team launches the main attack to fight with the fire. Victims who are trapped wish to be saved. Any of the three teams can lead victim out. Medical staff then provides medical treatment for the victims.

From the above sample scenario, we derive eight actors and twelve goals (both top goals and leaf goals). The goal model is depicted in figure \ref{fig:scenario-goal-model}. Table \ref{tbl:exp-cap-n-dep}(a) shows the actors' capabilities on satisfying a specific goal. Table \ref{tbl:exp-cap-n-dep}(b) shows the dependency relationship; for example, actor \emph{'A3: Fire commander'} can depend on actor \emph{'A8: Medical staff'} to perform the goal \emph{'G12: Provide medical treatment'}. 

Initially, actor \emph{'A1: Victim} requests goal \emph{'G10: Save victim'}, and actor \emph{'A3: Fire Commander'} requests goal \emph{'G1: Attack the fire'}.

Table \ref{tbl:exp-precedence} shows the precedence constraints between goals; for example, the goal \emph{'G11: Lead victim out'} can only be performed after the goal \emph{'G9: Locate victim'}, and \emph{'G12: Provide medical treatment'} can only be performed after \emph{'G11: Lead victim out'}.

%In this table, actors form table columns, and leaf goals form table rows. In each table cell, "D" means actor on that column can depend on other actors in the list to satisfy goal at the row; and 'P' means actor on the column can provide the appropriate goal at that row.


\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/scenario-goal-model}
    \caption{The scenario goal model.}
    \label{fig:scenario-goal-model}
\end{figure}

%\begin{table}[h]
%    \centering
%    \begin{tabular}{|p{4cm}|c|c|p{2.22cm}|c|c|c|c|c|}
%      \hline
%       Goal/Actor & A1 & A2 & A3 & A4 & A5 & A6 & A7 & A8 \\ \hline
%      G4: Launch main attack & & & D:[A7] & & & & P & \\ \hline
%      G5: Switch off gas electricity & & P & D:[A2,A5,A6] & & P & P &  & \\ \hline
%      G6: Use extinguisher & & P & D:[A2] & & &  &  & \\ \hline
%      G7: Cordon place & & & D:[A4] & P &  &  &  & \\ \hline
%      G8: Locate seat of fire & & & D:[A5,A6] & & P & P &  & \\ \hline
%      G9: Locate victim & & & D:[A5,A6] & & P & P &  & \\ \hline
%      G10: Save victim & D:[A3] & & & & & &  & \\ \hline
%      G11: Lead victim out & &  & D:[A5,A6,A7] & & P & P & P & \\ \hline
%      G12: Provide medical treatment & & & D:[A8] & & & &  & P \\ \hline
%    \end{tabular}
%    \vspace{0.2cm}
%    \small
%    \begin{minipage}{0.95\textwidth}
%        A1:Victim, A2:Fire warden, A3:Fire commander, A4:Police, A5:Blue team, A6:Green team, A7:Red team, A8:Medical staff
%    \end{minipage}
%    \caption{The number of desires regards to the static/non-static characteristic of goal and request.}
%    \label{tbl:abc}
%\end{table}

\begin{table}[h]
    \centering
    \subtable[Capabilities] {
        \small
        \begin{tabular}{|c|c|c|c|c|}
          \hline
           Actor & Goal & Effort & Time & Benefit \\ \hline
           A2 & G5  & 25 & 5  & 100 \\ \hline
           A2 & G6  & 25 & 20 & 100 \\ \hline
           A4 & G7  & 25 & 30 & 100 \\ \hline
           A5 & G5  & 25 & 5  & 100 \\ \hline
           A5 & G8  & 25 & 30 & 100 \\ \hline
           A5 &	G9  & 25 & 30 & 100 \\ \hline
           A5 &	G11 & 50 & 35 & 100 \\ \hline
           A6 &	G5  & 25 & 5  & 100 \\ \hline
           A6 &	G8  & 25 & 30 & 100 \\ \hline
           A6 &	G9  & 25 & 30 & 100 \\ \hline
           A6 &	G11 & 50 & 35 & 100 \\ \hline
           A7 &	G4  & 75 & 60 & 100 \\ \hline
           A7 &	G11 & 50 & 25 & 100 \\ \hline
           A7 &	G12 & 25 & 10 & 100 \\ \hline
        \end{tabular}
        \label{tbl:exp-capabilities}
    }
    \subtable[Dependency relationship]{
        \small
        \begin{tabular}{|c|c|c|}
            \hline
            Actor & Dependum & Dependee \\ \hline
            A1 & G10  & A3 \\ \hline
            A3 & G4   & A7 \\ \hline
            A3 & G5   & A2, A5, A6 \\ \hline
            A3 & G6   & A2 \\ \hline
            A3 & G7   & A4 \\ \hline
            A3 & G8   & A5, A6 \\ \hline
            A3 & G9   & A5, A6  \\ \hline
            A3 & G11  & A5, A6, A7 \\ \hline
            A3 & G12  & A8 \\ \hline
        \end{tabular}
        \label{tbl:exp-dependency}
    }
    \vspace{0.2cm}
    \footnotesize
    \begin{minipage}{0.95\textwidth}
        A1:Victim, A2:Fire warden, A3:Fire commander, A4:Police, A5:Blue team, A6:Green team, A7:Red team, A8:Medical staff
    \end{minipage}
    \caption{The actors' capabilities \subref{tbl:exp-capabilities}, and dependency relationship \subref{tbl:exp-dependency}}
    \label{tbl:exp-cap-n-dep}
\end{table}


\begin{table}[h]
    \centering
    \begin{tabular}{|c|c|}
      \hline
       Goal & Precedence goals \\ \hline
       G4 & G5, G8 \\ \hline
       G8 & G5 \\ \hline
       G9 & G5 \\ \hline
       G11 & G9 \\ \hline
       G12 & G11 \\ \hline
    \end{tabular}
    \caption{The precedence constraints between goals}
    \label{tbl:exp-precedence}
\end{table}


\subsection{Planning result}
Table \ref{tbl:exp-solutions} reports eight candidate solutions for the scenario (See appendix \ref{ch:PddlScript} for PDDL script and a fragment of solution \#1). Solutions are presented in rows, meanwhile columns are organizational leaf goals. Each table cell is the goal-to-actor assignment and the period of time when this goal is fulfilled.

To evaluate these solution, besides the BCQ evaluator (cf. section \ref{sec:BCQ}), we will simulates them over a set of event as follow. Suppose that during the fire fighting, when a solution is in execution for 40 minutes, the available budget (cf. section \ref{sec:ABC}) of the actor \emph{Green team} is suddenly decreased by 50 (event E1) for some reasons (e.g., some members of \emph{Green team} get injured). And at the minute of 70, the \emph{Blue team}'s budget is decreased by 50 as well (event E2).

To this extend we simulate all candidate solutions within the set of these two events to see their effects to the candidates. The table \ref{tbl:exp-simulate} shows the evolution of solutions with respect to events happen. In this table, the first column \emph{Solution} indicates the solution number. The \emph{Initial} determines the initial BCQ assessment value (BCQ for short). Next, column \emph{E1 (t=40)} and \emph{E2 (t=70)} present the solutions' BCQ at the moment events happen. The last column $t_{end}$ shows the time when each solution is accomplished. The graph shown in figure \ref{fig:exp-chart} is the quality of each solution over time.

According to table \ref{tbl:exp-simulate}, there five solutions (\#1, \#3, \#4, \#6, \#7) have the same score as 2.4096. Late on, when event \emph{E1} happens, there two solutions \#1 and \#6 are affected, their scores are decreased to 2.3256 and 2.2364, respectively. Next, event \emph{E2} arrives, solution \#3 suddenly goes to dead-end which means all the top goals are never satisfied. Again, solution \#6 is affected and decreased to 2.2599 while the others remain unaffected.

Based on this assessment, if total execution time is the most important, solution \#2 may be the best choice. Otherwise, both solution \#4 and \#7 are more suitable. Solution \#6 might be the poor choice since its quality is dropped down and the execution time is prolonged. In the meanwhile, solution \#3 is even worst because it leads to a dead-end.

\begin{table}
    \small
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
        \hline
        Solution & G4 & G5 & G6 & G7 & G8 & G9 & G11 & G12  \\ \hline
        \multirow{2}{*}{\#0} & A7 & A6 & \multirow{2}{*}{--} & A4 & A5 & A5 & A6 & A8   \\
            & 54--133 & 18--22 &  & 21--50 & 24--53 & 54--83 & 84--118 & 119--128   \\ \hline
        \multirow{2}{*}{\#1} & A7 & A2 & A2 & A4 & A5 & A5 & A5 & A8    \\
            & 57--116 & 18--22 & 23--42 & 24--53 & 27--56 & 57--86 & 87--121 & 122-131    \\\hline
        \multirow{2}{*}{\#2} & A7 & A2 & \multirow{2}{*}{--} & A4 & A6 & A6 & A5 & A8    \\
            & 54--113 & 18--22 &  & 21--50 & 24--53 & 54--83 & 84--118 &  119--128  \\\hline
        \multirow{2}{*}{\#3} & A7 & A2 & \multirow{2}{*}{--} & A4 & A6 & A6 & A5 & A8    \\
            & 54--113 & 18--22 &  & 21--50 & 24--53 & 54--83 & 84--118 &  119--128  \\ \hline
        \multirow{2}{*}{\#4} & A7 & A2 & A2 & A4 & A5 & A5 & A6 & A8    \\
            & 57--116 & 18--22 & 23--42 & 24--53 & 27--56 & 57--86 & 87--121 & 122-131   \\ \hline
        \multirow{2}{*}{\#5} & A7 & A6 & \multirow{2}{*}{--} & A4 & A5 & A5 & A5 & A8    \\
            & 51--110 & 12--16 &  & 18--47 & 21--50 & 51--80 & 81--115 &  116--125  \\ \hline
        \multirow{2}{*}{\#6} & A7 & A2 & A2 & A4 & A6 & A5 & A5 & A8    \\
            & 57--116 & 18--22 & 23--42 & 24--53 & 27--56 & 30--59 & 60--94 &  95--104  \\ \hline
        \multirow{2}{*}{\#7} & A7 & A2 & A2 & A4 & A6 & A6 & A5 & A8    \\
            & 57--116 & 18--22 & 23--42 & 24--53 & 27--56 & 57--86 & 87--121 &  122-131  \\ \hline
    \end{tabular}
    \caption{Eight candidate solutions for the scenario settings.}
    \label{tbl:exp-solutions}
\end{table}

\begin{table}
    \centering
    \begin{tabular} {|c|r|r|r|r|}
        \hline
        Solution  & Initial BCQ & E1 $(t=40)$ & E2 $(t=70)$ & $t_{end}$ \\ \hline
\#0 & 2.3179 & \multicolumn{1}{c|}{n/a} & \multicolumn{1}{c|}{dead} & \multicolumn{1}{c|}{--} \\ \hline
\#1 & 2.4096 & 2.3256 & \multicolumn{1}{c|}{n/a} & 179 \\ \hline
\#2 & 2.3179 & \multicolumn{1}{c|}{n/a} & \multicolumn{1}{c|}{n/a} & 128 \\ \hline
\#3 & 2.4096 & \multicolumn{1}{c|}{n/a} & \multicolumn{1}{c|}{dead} & \multicolumn{1}{c|}{--} \\ \hline
\#4 & 2.4096 & \multicolumn{1}{c|}{n/a} & \multicolumn{1}{c|}{n/a} & 131 \\ \hline
\#5 & 2.3256 & 2.3392 & \multicolumn{1}{c|}{dead} & \multicolumn{1}{c|}{--} \\ \hline
\#6 & 2.4096 & 2.2364 & 2.2599 & 209 \\ \hline
\#7 & 2.4096 & \multicolumn{1}{c|}{n/a} & \multicolumn{1}{c|}{n/a} & 131 \\ \hline
    \end{tabular}
    \vspace{0.2cm}
    \footnotesize
    \begin{center}
        n/a: not affected, dead: no available solution
    \end{center}
    \caption{The evolution of solutions according to events.}
    \label{tbl:exp-simulate}
\end{table}

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/exp-chart}
    \caption{Accomplishable solutions' quality according to events happen.}
    \label{fig:exp-chart}
\end{figure}

\section{Scalability}
In the domain of socio-network planning, the scalability of the planning problem and performance are very important. Obviously, the event-base simulators usually takes long time to complete than the simple ones. The table \ref{tbl:simul-step} shows the time consumed in each step of the event simulation. An event-simulation usually has there major steps: initialize the simulator, simulate the solution and replan when solution gets corrupt as events happen. Depend on the input solution and the events, these steps might happen several time. It is easy to realize that the time for (re)planning dominates times for other steps.

\begin{table}
    \centering
    \begin{tabular}{|l|r|r|}
      \hline
      Step & Time(ms) & Percentage(\%) \\ \hline
      Event-Simulation & 80.73181 & 100\% \\ \hline
      1. Initialize simulator & 0.02089 & 0.03\% \\ \hline
      2. Simulate solution & 0.853154 & 1.06\% \\ \hline
      3. Replan & 72.97947 & 90.40\% \\
      \hline
    \end{tabular}
    \caption{Consumed time for each step in event-based simulation.}
    \label{tbl:simul-step}
\end{table}

Hence, the performance and scalability of our framework relies heavily on the AI planner. This property depends on two factors. The first one, certainly, is the AI planner itself.  We do not discuss detail it here since we can simply choose the fastest planner on the market which supports PDDL standard. The second factor depend on how the problem domain is defined. More specific, it is the number of predicates used for describe the problem as well as the actions used by the planner.

Bryl et al \cite{BRYL-GIOR-MYLOP-09-REJ} has studied the scalability of an off-the-shelf AI planner tool, LPG-td, in their experiment. The planning part of our framework is based on that of \cite{BRYL-GIOR-MYLOP-09-REJ}. In which, the early evaluators are incorporated into the planning process. Therefore, in this experiment, we aim at studying how the growing complexity of planning problem influences the performance of the approach in comparison to Bryl's.

The planning problem files are conducted in the similar way of Bryl's, which are building from an elementary tree containing 4 decomposition levels, 15 goals ($G_i, i = \overline{1,15}$, 2 OR and 4 AND decomposition relations (see figure \ref{fig:exp-goal-model}). All problem files contain 6 actors $(A_i, i = \overline{1,6})$, organized into three levels with respect to the relations between them as of figure \ref{fig:exp-actor-relation}.  Overlapping capabilities is also introduced, namely, each leaf goal is satisfied by two actors.

\begin{figure}
    \centering
    \subfigure[]{
       \noindent
       \setlength{\parskip}{0cm}\small\fbox{
       \begin{minipage}[]{0.45\columnwidth}
           \begin{alltt}
(or\_subgoal2 G1 G2 G3)
(and\_subgoal3 G2 G4 G5 G6)
(or\_subgoal2 G4 G9 G10)
(and\_subgoal2 G5 G11 G12)
(and\_subgoal2 G3 G7 G8)
(and\_subgoal3 G7 G13 G14 G15)
           \end{alltt}
       \end{minipage}}
       \label{fig:exp-goal-model}
    }
    \hspace{0cm}
    \subfigure[]{
       \noindent
       \setlength{\parskip}{0cm}\small\fbox{
       \begin{minipage}[]{0.35\columnwidth}
           \begin{alltt}
(can\_depend\_on A1 A2)
(can\_depend\_on A1 A3)
(can\_depend\_on A2 A4)
(can\_depend\_on A2 A5)
(can\_depend\_on A3 A5)
(can\_depend\_on A3 A6)
           \end{alltt}
       \end{minipage}}
       \label{fig:exp-actor-relation}
    }
    \caption{Elementary goal tree \subref{fig:exp-goal-model}, and actors' relationship \subref{fig:exp-actor-relation}}
\end{figure}

In the experimental result in table \ref{tbl:exp-multi-tree}, we study the situation that the planning problem grows in breadth; that is, the number of top goals increase. $N_{trees}$ represents the number of elementary trees in the problem file, $N^B_{fact}, t^{B}_{total}$ are the number of facts in the problem file and the total planning time of Bryl's approach, respectively. And $N^J_{fact}, t^{J}_{total}$ are those of our approach. The two last columns, $D_{fact} = \dfrac{N^J_{fact} - N^B_{fact}}{N^B_{fact}}$ shows the difference of number of facts between two approach, and $D_{total} = \dfrac{t^J_{total} - t^B_{total}}{t^B_{total}}$ is that total time. As shown in the table, our approach has the same scalability of Bryl's. In our approach, since the number of facts in the planning problem file is approximate twice greater than that of Bryl's. Therefore, the difference of total time is not surprisingly around 20\% slower.

\begin{table}[h]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|}
      \hline
      $N_{trees}$ & $N^B_{fact}$ & $N^J_{fact}$ & $t^{B}_{total}$ & $t^{J}_{total}$ & $D_{fact}$ & $D_{total}$ \\ \hline
        1 & 31 & 91 & 0.06 & 0.08 & 1.94 & 0.33\\ \hline
        2 & 56 & 170 & 0.53 & 0.64 & 2.04 & 0.21\\ \hline
        3 & 81 & 249 & 2.48 & 2.51 & 2.07 & 0.01\\ \hline
        4 & 106 & 328 & 3.7 & 3.73 & 2.09 & 0.01\\ \hline
        5 & 131 & 407 & 8.52 & 10.17 & 2.11 & 0.19\\ \hline
        6 & 156 & 486 & 11.89 & 15.23 & 2.12 & 0.28\\ \hline
        7 & 181 & 565 & 15.3 & 19.33 & 2.12 & 0.26\\ \hline
        8 & 206 & 644 & 20.25 & 25.21 & 2.13 & 0.24\\ \hline
        9 & 231 & 723 & 28.09 & 31.39 & 2.13 & 0.12\\ \hline
        10 & 256 & 802 & 40.01 & 45.21 & 2.13 & 0.13\\ \hline
        11 & 281 & 881 & 58.39 & 63.07 & 2.14 & 0.08\\ \hline
        12 & 306 & 960 & ERR & ERR & -- & -- \\ \hline
    \end{tabular}
    \caption{Experimental result: increasing number of elementary goal trees.}
    \label{tbl:exp-multi-tree}
\end{table}

On the other hand, the table \ref{tbl:exp-single-tree} reports experimental result of increasing the problem complexity in depth; it means that the level of the elementary goal tree is increased by adding additional goal to leaf goals. The meaning of each column is exactly the same as that of table \ref{tbl:exp-multi-tree}. The reported numbers are a little bit suppress since our approach and Bryl's are approximately the same. The reason could be that our approach has a the greater parsing time and the lower searching time compare with that of Bryl's. The reason of greater parsing time is obliviously because of the larger amount of facts. Meanwhile, additional early evaluators helps the planner to cut down the search space; it lead to the smaller searching time.

\begin{table}[h]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|}
        \hline
        $Level$ & $N^B_{fact}$ & $N^J_{fact}$ & $t^{B}_{total}$ & $t^{J}_{total}$ & $D_{fact}$ & $D_{total}$ \\ \hline
        13 & 139 & 415 & 6.21 & 4.15 & 1.99 & -0.33  \\ \hline
        14 & 151 & 451 & 8.47 & 5.85 & 1.99 & -0.31  \\ \hline
        15 & 163 & 487 & 9.34 & 10.37 & 1.99 & 0.11  \\ \hline
        16 & 175 & 523 & 10.75 & 9.91 & 1.99 & -0.08  \\ \hline
        17 & 187 & 559 & 13.95 & 12.15 & 1.99 & -0.13  \\ \hline
        18 & 199 & 595 & 13.14 & 13.71 & 1.99 & 0.04  \\ \hline
        19 & 211 & 631 & 15.76 & 18.63 & 1.99 & 0.18  \\ \hline
        20 & 223 & 667 & 19.31 & 19.7 & 1.99 & 0.02  \\ \hline
        21 & 235 & 703 & 23.07 & 21.12 & 1.99 & -0.08  \\ \hline
        22 & 247 & 739 & 27.33 & 25.8 & 1.99 & -0.06  \\ \hline
        23 & 259 & 775 & 31.51 & 30.17 & 1.99 & -0.04  \\ \hline
        24 & 271 & 811 & ERR & ERR & -- & --  \\ \hline
    \end{tabular}
    \caption{Experimental result: increasing level of elementary goal trees.}
    \label{tbl:exp-single-tree}
\end{table} 